Various techniques have been proposed to provide a mechanism to fairly and efficiently allocate a common resource to multiclass traffic having stochastic (non-deterministic) arrival processes whose variability precludes deterministic scheduling. For each technique, the aim is to provide a fair mechanism in which each class is guaranteed a certain throughput, independent of the demand coming from the other classes. The technique must also be efficient, in that capacity is fully utilized whenever there is demand for it, and be capable of operating in an "open loop" configuration in which the access control mechanism does not receive status information from the shared resource.
For example, consider a telecommunications network that can handle a limited number of packetized communications messages. The network receives packet traffic from numerous customers having communications and business needs that differ from each other and that change with time. The customers are willing to contract for different levels of minimum use of the network, which must be guaranteed by the network provider. Both the network provider and the customers would like to use any excess network capacity for traffic demands made by users that exceed the contracted minimum. Once packets are accepted into the network, they must be transmitted to their destinations; no feedback is available to the admission control mechanism regarding the network status.
In the foregoing scenario, the demand posed on the network varies in some random fashion, since the customers originate traffic independently of each other. This inherent randomness gives rise to a conflict between the desire to run an efficient network operation, and the need to guarantee every customer is contracted network access as well as a fair share of any excess capacity in the network. The same problem exists in other telecommunications and in data processing environments: a pool of telephone agents, bandwidth in a communication channel, and processing time in a CPU, are examples of limited resources facing access requests from plural sources.
One common strategy that is known in the prior art is to partition the entire resource into designated shares for each class. Obviously, this approach has the positive quality of preventing one class from interfering with another; however, it also has the negative quality of inefficient utilization of the resources, in that it fails to allocate idle resources. The logical complement to complete partitioning is complete sharing, which yields efficient utilization of the resource but not protection of one class from another, since it does not guarantee each class its fair share.
Another approach to access control that may attain positive qualities of partitioning and sharing is based on the notion that each class may have a portion of the resource dedicated (reserved) for it, but the sum of all of the capacity reservations are less than the total capacity. The unreserved capacity is then shared on a first-come, first-served basis. Unfortunately, such a control scheme has a limited efficiency, since unused resources can be wasted. Also, the system parameters need to be tuned to the specific arrival processes. In contrast, what is desired is an admission control technique that requires no feedback information, and that can accommodate a very wide range of arrival processes.
Another access regulation mechanism, provided as part of a new service originated by Bell Communications Research, Inc. called Switched Multi-Megabit Data Service (SMDS), uses a credit bank to keep track of the resources used by a subscriber to be sure that an agreed upon usage limit is not exceeded. However, this policing mechanism is useful only for a single class of traffic, and does not contemplate sharing of excess capacity with multiple other subscribers.
An overload control used in AT&T's #5ESS.RTM. switch, known as the "Routing and Terminal Administration" (RTA) throttle, uses a scheme designed for two classes--line originations and trunk originations. While this scheme does have a sharing feature whereby excess capacity from one class can be used by another class, it cannot work for an arbitrary number of classes, and the specific process used for the two classes suffers because it is specifically designed only for certain limited applications.
Yet other approaches are described in several United States patents. Specifically, U.S. Pat. No. 5,014,265 issued May 7, 1991, to Ellen L. Hahne et al. entitled "Method and Apparatus for Congestion Control in a Data Network" describes a method of controlling congestion in a virtual circuit packet network. An initial packet buffer is assigned to each virtual circuit at each node into which incoming packets are stored and later removed for forward routing. If a larger buffer is desired for a virtual circuit to service a larger amount of data, then additional buffer space is dynamically allocated selectively to the virtual circuit on demand if each node has sufficient unallocated buffer space to fill the request. In one embodiment, the criterion for dynamic allocation is based on the amount of data buffered at the data source. In alternative embodiments, the criteria for dynamic allocation may be further based on the amount of data buffered at each node for a virtual circuit and the total amount of free buffer space at each node of a virtual circuit. Signaling protocols are disclosed whereby data sources and virtual circuit nodes maintain consistent information describing the buffer allocations at all times. Because the Hahne approach presumes that the control mechanism has detailed knowledge of the state of the resource being controlled (via the signaling protocol), it is not useful where such knowledge is not available.
Numerous other references exist that describe flow control mechanisms useful in packet networks. Some of these mechanisms are intended to prevent overflow at a receiver buffer, and are not directed to regulation of admission to a shared resource. Other techniques involve flow control methods that try to protect resources by establishing an admission window that depends upon feedback information, and that cannot operate on an open loop basis. Yet other techniques do operate on an open loop (pacing control) basis, but do not satisfy other requirements that are described above. Examples of these references are U.S. Pat. No. 4,984,264 issued to Yasuhiro Katsube on Jan. 8, 1991, which describes a call admission control and cell flow monitoring method, U.S. Pat. No. 4,769,810 issued to Adrian E. Eckberg Jr., entitled "Packet Switching System Arranged for Congestion Control through Bandwidth Management", and U.S. Pat. No. 4,613,359 issued to Michael L. Fontenot and entitled "Adaptive Preferential Flow Control for Packet Switching System".